// 115. 不同的子序列
// 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
// 题目数据保证答案符合 32 位带符号整数范围。

// 这道题目如果换种方式解读的话，就好理解了
// s 的子序列中 t 出现的个数，可以解读为：
// s 中的字符能凑几个 t ？
/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function (s, t) {
  const len1 = s.length
  const len2 = t.length

  // dp[i][j] 表示，s 前 i 个字符匹配上 t[:j + 1] 的个数
  const dp = new Array(len1 + 1).fill(0).map(() => new Array(len2 + 1).fill(0))

  // 如果 t 是个空字符串，那 s 怎么都能匹配的上，所以设置为 1
  for (let i = 0; i <= len1; i++) {
    dp[i][0] = 1
  }

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      // 在采样过程中，如果 s 尾部字符和 t 尾部字符相等
      // 这时候可以考虑成两种情况
      let p1 = 0
      let p2 = 0

      // 1. 将 s 和 t 尾部字符凑一起，这时情况数和不考虑尾部的情况数一样
      if (s[i - 1] === t[j - 1]) {
        p1 = dp[i - 1][j - 1]
      }

      // 2. 如果不将 s 和 t 尾部字符凑一起，这时候相当于拿旧的 s 凑新的 t
      p2 = dp[i - 1][j]

      dp[i][j] = p1 + p2
    }
  }

  return dp[len1][len2]
}

console.log(
  numDistinct(
    "rabbbit",
    "rabbit"
  )
)










